CAMWI: Detecting protein complexes using weighted clustering coefficient and weighted density

Detection of protein complexes is very important to understand the principles of cellular organization and function. Recently, large protein–protein interactions (PPIs) networks have become available using high-throughput experimental techniques. These networks make it possible to develop computational methods for protein complex detection. Most of the current methods rely on the assumption that protein complex as a module has dense structure. However complexes have core-attachment structure and proteins in a complex core share a high degree of functional similarity, so it expects that a core has high weighted density. In this paper we present a Core-Attachment based method for protein complex detection from Weighted PPI Interactions using clustering coefficient and weighted density. Experimental results show that the proposed method, CAMWI improves the accuracy of protein complex detection.     

Local reconstruction of low‐rank matrices and subspaces

We study the problem of reconstructing a low‐rank matrix, where the input is an n × m matrix M over a field and the goal is to reconstruct a (near‐optimal) matrix that is low‐rank and close to M under some distance function Δ. Furthermore, the reconstruction must be local, i.e., provides access to any desired entry of by reading only a few entries of the input M (ideally, independent of the matrix dimensions n and m). Our formulation of this problem is inspired by the local reconstruction framework of Saks and Seshadhri (SICOMP, 2010). Our main result is a local reconstruction algorithm for the case where Δ is the normalized Hamming distance (between matrices). Given M that is ‐close to a matrix of rank (together with d and ), this algorithm computes with high probability a rank‐d matrix that is ‐close to M. This is a local algorithm that proceeds in two phases. The preprocessing phase reads only random entries of M, and stores a small data structure. The query phase deterministically outputs a desired entry by reading only the data structure and 2d additional entries of M. We also consider local reconstruction in an easier setting, where the algorithm can read an entire matrix column in a single operation. When Δ is the normalized Hamming distance between vectors, we derive an algorithm that runs in polynomial time by applying our main result for matrix reconstruction. For comparison, when Δ is the truncated Euclidean distance and , we analyze sampling algorithms by using statistical learning tools. A preliminary version of this paper appears appears in ECCC, see: http://eccc.hpi-web.de/report/2015/128/ © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 607–630, 2017     

Constructing near spanning trees with few local inspections

Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let G be a connected bounded‐degree graph. Given an edge e in G we would like to decide whether e belongs to a connected subgraph consisting of edges (for a prespecified constant ), where the decision for different edges should be consistent with the same subgraph . Can this task be performed by inspecting only a constant number of edges in G ? Our main results are:

• We show that if every t‐vertex subgraph of G has expansion then one can (deterministically) construct a sparse spanning subgraph of G using few inspections. To this end we analyze a “local” version of a famous minimum‐weight spanning tree algorithm.
• We show that the above expansion requirement is sharp even when allowing randomization. To this end we construct a family of 3‐regular graphs of high girth, in which every t‐vertex subgraph has expansion . We prove that for this family of graphs, any local algorithm for the sparse spanning graph problem requires inspecting a number of edges which is proportional to the girth.

© 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 183–200, 2017     

Finding Adam in random growing trees

We investigate algorithms to find the first vertex in large trees generated by either the uniform attachment or preferential attachment model. We require the algorithm to output a set of K vertices, such that, with probability at least , the first vertex is in this set. We show that for any ε, there exist such algorithms with K independent of the size of the input tree. Moreover, we provide almost tight bounds for the best value of K as a function of ε. In the uniform attachment case we show that the optimal K is subpolynomial in , and that it has to be at least superpolylogarithmic. On the other hand, the preferential attachment case is exponentially harder, as we prove that the best K is polynomial in . We conclude the paper with several open problems. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 158–172, 2017     

A Cross-Entropy Approach to the Estimation of Generalized Linear Multilevel Models

In this article, we use the cross-entropy method for noisy optimization for fitting generalized linear multilevel models through maximum likelihood. We propose specifications of the instrumental distributions for positive and bounded parameters that improve the computational performance. We also introduce a new stopping criterion, which has the advantage of being problem-independent. In a second step we find, by means of extensive Monte Carlo experiments, the most suitable values of the input parameters of the algorithm. Finally, we compare the method to the benchmark estimation technique based on numerical integration. The cross-entropy approach turns out to be preferable from both the statistical and the computational point of view. In the last part of the article, the method is used to model the probability of firm exits in the healthcare industry in Italy. Supplemental materials are available online.     

Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems

Semidefinite relaxations of certain combinatorial optimization problems lead to approximation algorithms with performance guarantees. For large-scale problems, it may not be computationally feasible to solve the semidefinite relaxations to optimality. In this paper, we investigate the effect on the performance guarantees of an approximate solution to the semidefinite relaxation for MaxCut, Max2Sat, and Max3Sat. We show that it is possible to make simple modifications to the approximate solutions and obtain performance guarantees that depend linearly on the most negative eigenvalue of the approximate solution, the size of the problem, and the duality gap. In every case, we recover the original performance guarantees in the limit as the solution approaches the optimal solution to the semidefinite relaxation.     

普适的基于能量的分块局域激发态聚类算法

在普适的基于能量的分块(GEBF)方法的框架下, 大体系的局域激发(LE)能可通过一系列活性子体系激发能的线性组合近似得到, 从而有效降低了计算的时间标度. 然而, 在体系的局域激发具有多个激发态的情形下, 如何有效识别所有活性子体系的激发特征并将其组合是一个挑战. 提出了一种基于局域激发态聚类的算法. 该方案基于空穴-电子分析和基于密度的聚类(DBSCAN)机器学习算法, 可以自动地聚合不同子体系中最相似的激发态并组合得到相应的局域激发态能量或激发能. 结合该算法改进的LE-GEBF方法在荧光分子衍生物、 荧光染料-水团簇及绿色荧光蛋白模型体系的计算中均获得了令人满意的结果. 该算法有望大大提升LE-GEBF方法在计算局域激发时的稳定性和准确性, 并可以有效处理吸收光谱具有多重峰的大体系.     

概说并行计算结构力学

基于向量机（ｖｅｃｔｏｒｃｏｍｐｕｔｅｒｓ）和并行机（ｐａｒａｌｌｅｌｃｏｍｐｕｔｅｒｓ）两大类并行计算机，对线性静力和动力问题，非线性静力和动力问题，本文概说了相应于这两大类并行机一般的求解方法。     

A continuum analysis of charge induced ferroelectric domain wall motions

A continuum model is presented for the motion of a domain wall in a plane 90°-domain configuration subjected to an isolated extrinsic charge near the surface of a ferroelectric single crystal. Local pinning is postulated for the kinetic law. Before the appearance of the extrinsic charge, all polarization surface charges are taken to be neutralized by environmental charges. The domain wall motion after the appearance of the extrinsic charge is assumed to proceed sufficiently fast without any significant conductive currents on the surface or in the interior of the crystal such that new surface and interface polarization charges remain unscreened and contribute to the ferroelectric anisotropy energy. A non-admissible divergence of the electric field and consequently of the local thermodynamic driving force and of the domain wall velocity appears in the model if the domain wall charged by interface polarization charges intersects the crystal surface charged by surface polarization charges under an arbitrary angle. The physically possible domain wall angle is identified using the condition of a non-divergent driving force. The ferroelectric anisotropy energy and an intrinsic surface energy of the domain wall, however, do not provide stability of the domain wall trajectory against an unlimited increase of its curvature at the surface. The problem has been solved conceptually by proper account of the domain wall bending energy. Numerical and dimensional analysis explain also why domain walls driven by extrinsic charges remain almost straight in soft ferroelectrics.     

建筑结构最优阻尼及最优配置研究

利用阻尼来抗震是建筑物最简单的抗震方法,当在阻尼数目少于楼层数时,为使所布置的阻尼达到最优的抗震效果,本文开发了两种最优阻尼配置方法。第一种方法是根据临界激励法确定计算所有可能布置位置中的临界阻尼,选择最小的临界阻尼位置作为最优配置。第二种方法则是根据给定阻尼,计算最优控制效果以确定最优阻尼配置。然后根据实代码遗传算法,在结构抗震效果基本保证的前提下,寻找最优阻尼以降低结构总的阻尼增量。最后给出了一个计算实例。